1. Field of the Invention
The present invention relates to a memory control apparatus, a program, and a method for controlling access to a shared memory for each transaction.
2. Description of Related Art
In a computer system, multithreading is used. In multithreading, multiple threads perform multiple processes in parallel. In a computer system in which multithreading is used, when each of the multiple threads accesses a shared variable shared by the multiple threads, the thread and the other threads need to be synchronized. For example, exclusive control in which a lock is used is known as a synchronization method in multithreading. However, in exclusive control in which a lock is used, when an area in which processing is performed exclusively (i.e., a critical section) becomes large, the parallelism of processing by multithreading is impaired, and thus the performance is decreased.
A transactional memory is a synchronization mechanism for solving such a problem. In a transactional memory, a critical section is treated as a transaction, and memory access in the transaction is handled atomically. Specifically, in a transactional memory, memory access to a shared variable in a transaction is logged, and the change of the value of the shared variable in the transaction is made invisible to the other transactions until the transaction is committed. Then, in the transactional memory, any conflict of access to the shared variable is checked at the end of the transaction. When no conflict has occurred, the transaction is committed, and the change of the value of the shared variable is put into effect. When a conflict has occurred, the transaction is rolled back.
FIG. 1 shows the flow of processing in a case where two transactions T1 and T2 read, modify, and write the value of a shared variable V in parallel. For example, the change of the value of the shared variable V in the transaction T1 is committed, and the transaction T2 reads the value of the shared variable V, which has not been committed in the transaction T1. In this case, conflict of memory access to the shared variable V occurs between the transactions T1 and T2, and thus the commit of the transaction T2 fails. The transaction T2, the commit of which has failed, is rolled back. Specifically, the transaction T2 is re-executed after the state of memory access in the transaction T2 is rolled back to that at the start of the transaction T2.
See T. Harris and S. Stipic, “Abstract nested Transactions”, TRANSACT 2007, at Internet URL http://www.cs.rochester.edu/meetings/TRANSACT07/papers/harris.pdf.
In such a transactional memory, when read-modify-write operations in which the value of a variable is read, and then the read value is written back after being subjected to an operation occur in a transaction, rollback may frequently occur. The larger the size of a transaction is, the heavier overhead due to rollback is. Thus, when a large-sized transaction includes read-modify-write operations, the execution efficiency of programs is decreased.
Harris and Stipic disclose a method in which, when the commit of a transaction has failed, the entire transaction need not be re-executed, as a method for preventing such a problem. In the method disclosed by them, a programmer sets an abstract nested transaction (ANT) block in code that constitutes a transaction. Then, the log of execution of the ANT block and the log of execution of part of the code other than the ANT block are separately obtained. When only memory access in the ANT block causes rollback, re-execution of only the ANT block is attempted. Then, the result of the initial execution is compared with the result of the re-execution. When the re-execution does not affect the result of execution of a program, the transaction is committed on the basis of the result of the re-execution.
However, in the method disclosed by Harris and Stipic, a programmer needs to specify points that cause rollback, for example, read-modify-write operations. Thus, when rollback frequently occurs due to read-modify-write operations in a library the source code of which does not exist, re-execution of the entire transaction cannot be prevented.